home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-01 / snip0493.zip / PERMUTE2.C < prev    next >
C/C++ Source or Header  |  1993-04-05  |  2KB  |  80 lines
  1. /*
  2. **  PERMUTE.C - prints all permutations of an input string
  3. **
  4. **  public domain demo by Jon Guthrie
  5. */
  6.  
  7. #include    <string.h>
  8. #include    <stdlib.h>
  9. #include    <stdio.h>
  10.  
  11. int     charcmp(char *, char *);
  12.  
  13. void    permute(char *, int, int);
  14.  
  15. int     main(int argc, char *argv[])
  16. {
  17.       int length;
  18.  
  19.       if (2 > argc)
  20.       {
  21.             puts("Usage: PERMUTE string");
  22.             abort();
  23.       }
  24.       
  25.       length = strlen(argv[1]);
  26.  
  27.       /* It only works if they're printed in order */
  28.  
  29.       qsort(argv[1], length, 1, (int(*)(const void *, const void *))charcmp);
  30.  
  31.       permute(argv[1], 0, length);
  32.       return 0;
  33. }
  34.  
  35.  
  36. /*
  37. **  This function prints all of the permutations of string "array"
  38. **  (which has length "len") starting at "start."
  39. */
  40.  
  41. void    permute(char *array, int start, int len)
  42. {
  43.       int j;
  44.       char    *s;
  45.  
  46.       if(start < len)
  47.       {
  48.             if(NULL == (s = malloc(len)))
  49.             {
  50.                   printf("\n\nMemory error!!!\a\a\n");
  51.                   abort();
  52.             }
  53.  
  54.             strcpy(s, array);
  55.             for(j=start ; j<len ; ++j)
  56.             {
  57.                   int     temp;
  58.  
  59.                   if((j == start) || (s[j] != s[start]))
  60.                   {     /* For each character that's different    */
  61.                         /* Swap the next first character with...  */
  62.                         /* the current first                      */
  63.                         temp = s[j];
  64.                         s[j] = s[start];
  65.                         s[start] = temp;
  66.                         permute(s, start+1, len);
  67.                   }
  68.             }
  69.             free(s);
  70.       }
  71.       else    puts(array);
  72. }
  73.  
  74.  
  75.  
  76. int charcmp(char *a, char *b)
  77. {
  78.       return(*a - *b);
  79. }
  80.